import java.util.*;

public class BinaryTree<T extends Comparable<T>> {
    private T data;
    private BinaryTree<T> left, right;
    private BinaryTree<T> parent; // Useful only in task 4.6

    public BinaryTree(T data) {
        this.data = data;
    }

    public BinaryTree(T data, BinaryTree<T> left, BinaryTree<T> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    /*
        4.5 Implement a function to check if a binary tree is a binary search tree.
     */
    public static boolean isBST(BinaryTree<Integer> root) {
        if (root == null) return true;
        return checkBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private static boolean checkBST(BinaryTree<Integer> root, int minValue, int maxValue) {
        if (root == null) return true;
        if (root.data.compareTo(minValue) < 0 || root.data.compareTo(maxValue) > 0) return false;
        return checkBST(root.left, minValue, root.data) && checkBST(root.right, root.data, maxValue);
    }

    /*
       4.3 Given a sorted (increasing order) array with unique integer elements,
       write an algorithm to create a binary search tree with minimal height.
    */
    public static <T extends Comparable<T>> BinaryTree<T> buildTreeFromArray(T[] a) {
        if (a == null || a.length == 0) return null;
        return buildTreeFromArrayRange(a, 0, a.length - 1);
    }

    public static <T extends Comparable<T>> BinaryTree<T> buildTreeFromArrayRange(T[] a, int left, int right) {
        if (a == null || right < left) return null;
        if (right == left) return new BinaryTree<T>(a[right]);
        final int middle = left + (right - left) / 2;
        return new BinaryTree<T>(a[middle], buildTreeFromArrayRange(a, left, middle - 1), buildTreeFromArrayRange(a, middle + 1, right));
    }

    /*
        4.4 Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth
        (e.g., if you have a tree with depth D, you'll have D linked lists).
     */
    public static <T extends Comparable<T>> List<LinkedList<T>> getListOfNodesLevelList(BinaryTree<T> root) {
        if (root == null) return null;

        List<LinkedList<T>> result = new LinkedList<LinkedList<T>>();
        addRootLevel(root, result);

        Queue<BinaryTree<T>> curLevelNodes = new LinkedList<BinaryTree<T>>(), nextLevelNodes = new LinkedList<BinaryTree<T>>();
        curLevelNodes.add(root);

        while (!curLevelNodes.isEmpty()) {
            BinaryTree<T> currentNode = curLevelNodes.poll();
            if (currentNode.left != null) nextLevelNodes.add(currentNode.left);
            if (currentNode.right != null) nextLevelNodes.add(currentNode.right);
            if (curLevelNodes.isEmpty()) {
                if (!nextLevelNodes.isEmpty()) {
                    LinkedList<T> oneLevelNodes = new LinkedList<T>();
                    for (BinaryTree<T> treeNode : nextLevelNodes) oneLevelNodes.add(treeNode.data);
                    result.add(oneLevelNodes);
                }
                curLevelNodes = nextLevelNodes;
                nextLevelNodes = new LinkedList<BinaryTree<T>>();
            }
        }
        return Collections.unmodifiableList(result);
    }

    private static <T extends Comparable<T>> void addRootLevel(BinaryTree<T> root, List<LinkedList<T>> result) {
        LinkedList<T> rootLevelList = new LinkedList<T>();
        rootLevelList.add(root.data);
        result.add(rootLevelList);
    }

    public static <T extends Comparable<T>> void setTheParentFields(BinaryTree<T> root, BinaryTree<T> parent) {
        if (root == null) return;
        root.parent = parent;
        if (root.left != null) setTheParentFields(root.left, root);
        if (root.right != null) setTheParentFields(root.right, root);
    }

    /*
        4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree.
        Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
     */
    public static <T extends Comparable<T>> BinaryTree<T> getGCAwithParent(BinaryTree<T> root, BinaryTree<T> node1, BinaryTree<T> node2) {
        if (root == null) return null;
        if (node1 == null || node2 == null) return root;
        Set<BinaryTree<T>> visitedNodes = new HashSet<BinaryTree<T>>();
        while (node1.parent != null) {
            visitedNodes.add(node1);
            node1 = node1.parent;
        }
        if (node1 != root) return null; // We were given the node from outside the tree

        while (node2.parent != null) {
            if (visitedNodes.contains(node2)) return node2;
            node2 = node2.parent;
        }
        if (node2 != root) return null; // We were given the node from outside the tree
        return root;
    }

    public static <T extends Comparable<T>> BinaryTree<T> getFirstCommonAncestor(BinaryTree<T> root, BinaryTree<T> node1, BinaryTree<T> node2) {
        if (root == null) return null;
        if (!covers(root, node1) || !covers(root, node2)) return null;
        return getFCA(root, node1, node2);
    }

    private static <T extends Comparable<T>> BinaryTree<T> getFCA(BinaryTree<T> root, BinaryTree<T> node1, BinaryTree<T> node2) {
        if (root == null) return null;
        if (node1 == null || node2 == null) return root;
        boolean coversNode1 = covers(root, node1);
        boolean coversNode2 = covers(root, node2);
        if (coversNode1 && coversNode2) return root;
        if (coversNode1) return getFCA(root.left, node1, node2);
        else return getFCA(root.right, node1, node2);

    }

    private static <T extends Comparable<T>> boolean covers(BinaryTree<T> root, BinaryTree<T> node) {
        if (root == null) return false;
        if (root == node) return true;
        return (covers(root.left, node) || covers(root.right, node));
    }

    /*
        4.8 You have two very large binary trees: Tl, with millions of nodes, and T2, with hundreds of nodes.
        Create an algorithm to decide ifT2 is a subtree of Tl. A tree T2 is a subtree of Tl if there exists a node n
        in Tl such that the subtree of n is identical to T2. That is, if you cut off the tree at node n,
        the two trees would be identical.
    */
    public static <T extends Comparable<T>> boolean isSubtree(BinaryTree<T> bigTree, BinaryTree<T> treeToSearch) {
        if (bigTree == null) return false;
        if (treeToSearch == null) return true;
        if (bigTree.data.compareTo(treeToSearch.data) == 0) return matchTheTrees(bigTree, treeToSearch);
        return isSubtree(bigTree.left, treeToSearch) || isSubtree(bigTree.right, treeToSearch);
    }

    private static <T extends Comparable<T>> boolean matchTheTrees(BinaryTree<T> root1, BinaryTree<T> root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.data.compareTo(root2.data) != 0) return false;
        else return matchTheTrees(root1.left, root2.left) && matchTheTrees(root1.right, root2.right);
    }

    /*
        4.9 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths
        which sum to a given value. The path does not need to  start or end at the root or a leaf.
     */
    public static void printPathsWithGivenSum(BinaryTree<Integer> root, int sum) {
        int depth = getTreeDepth(root);
        int[] path = new int[depth];
        int level = 0;
        findPathsWithGivenSum(root, path, level, sum);
    }

    private static void findPathsWithGivenSum(BinaryTree<Integer> root, int[] path, int level, int sum) {
        if (root == null) return;
        path[level] = root.data;
        int curLevelSum = 0;
        for (int i = level; i >= 0; i--) {
            curLevelSum += path[i];
            if (curLevelSum == sum) {
                System.out.println("The sum (" + sum + ") is attained: " + Arrays.toString(Arrays.copyOfRange(path, i,level+1)));
            }
        }
        findPathsWithGivenSum(root.left, path, level + 1, sum);
        findPathsWithGivenSum(root.right, path, level + 1, sum);
    }

    private static <T extends Comparable<T>> int getTreeDepth(BinaryTree<T> root) {
        if (root == null) return 0;
        return Math.max(getTreeDepth(root.left), getTreeDepth(root.right)) + 1;
    }

    /*
      4.1 Implement a function to check if a binary tree is balanced. For the purposes of this
      question, a balanced tree is defined to be a tree such that the heights of the two
      subtrees of any node never differ by more than one.
   */
    public boolean isBalanced() {
        if (this.right == null && this.left == null) return true;
        return subTreeHeight(this) != -1;

    }

    private int subTreeHeight(BinaryTree<T> root) {
        if (root == null) return 0;
        int leftSubTreeHeight = subTreeHeight(root.left);
        if (leftSubTreeHeight == -1) return -1;

        int rightSubTreeHeight = subTreeHeight(root.right);
        if (rightSubTreeHeight == -1) return -1;

        if (Math.abs(rightSubTreeHeight - leftSubTreeHeight) > 1) return -1;
        return Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
    }

    @Override
    public String toString() {
        return "BinaryTree{" +
                "data=" + data +
                (left == null ? "" : (", left=" + left)) +
                (right == null ? "" : (", right=" + right)) +
                '}';
    }

    public BinaryTree<T> search(T node) {
        if (this.data == null) return null;
        if (this.data.compareTo(node) == 0) return this;
        if (this.data.compareTo(node) < 0 && this.right != null) return this.right.search(node);
        if (this.data.compareTo(node) > 0 && this.left != null) return this.left.search(node);
        return null;
    }

    /*
        4.6 Write an algorithm to find the'next'node (i.e., in-order successor) of a given node
        in a binary search tree. You may assume that each node has a link to its parent
     */
    public BinaryTree<T> getNextNode() {
        if (this.right != null) return mostLeft(this.right);
        BinaryTree<T> parentNode = this.parent;
        BinaryTree<T> currentNode = this;
        while (parentNode != null && parentNode.right == currentNode) {
            currentNode = parentNode;
            parentNode = parentNode.parent;
        }
        return parentNode;
    }

    private BinaryTree<T> mostLeft(BinaryTree<T> root) {
        while (root.left != null) root = root.left;
        return root;
    }
}
